Explanation of the Nested Set Model Code in Frappe

Nested Set Model (NSM) for hierarchical data structures in the Frappe Framework. It helps manage tree structures, ensuring efficient querying and modification of hierarchical data.

Key Features of the Code

1. Maintains Left (lft) and Right (rgt) indexes:

   • Each node in the hierarchy is assigned lft and rgt values.
   • lft and rgt define a range that encompasses all its children.

2. Implements Common Tree Operations:

   • Adding Nodes: Ensures correct positioning of new nodes.
   • Moving Nodes: Repositions nodes and updates indices.
   • Deleting Nodes: Removes nodes and adjusts the tree structure.
   • Rebuilding Tree: Ensures the tree is properly structured after modifications.

3. Prevents Errors:

   • Loops Prevention: Ensures a node cannot be its own ancestor.
   • Multiple Roots Prevention: Ensures only one root node is allowed.
   • Child Existence Validation: Prevents deletion of nodes that have children.

4. Database Optimization:

   • Uses SQL-based queries via frappe.qb for efficient tree management.
   • Implements for_update=True to prevent race conditions.

How the Code Works

1. update_nsm(doc)

   • Called in on_update to maintain the tree structure.
   • Checks if the node is new or moved, then updates indexes.

2. update_add_node(doc, parent, parent_field)

   • Assigns lft and rgt values for new nodes.
   • Updates all existing nodes accordingly.

3. update_move_node(doc, parent_field)

   • Handles node repositioning.
   • Adjusts lft and rgt values based on the new parent.

4. rebuild_tree(doctype)

   • Ensures the tree remains correctly structured after modifications.

5. remove_subtree(doctype, name, throw=True)

   • Deletes a node and all its descendants while maintaining tree consistency.

6. validate_loop(doctype, name, lft, rgt)

   • Ensures that a node is not assigned to its own descendants.

User Manual: Managing Tree Structures in Frappe

This manual provides step-by-step guidance on using the Nested Set Model (NSM) in Frappe to manage tree structures.

1. Setting Up Nested Set Model

A. Required Fields

Ensure your Doctype has the following fields: - lft (Integer) → Left index. - rgt (Integer) → Right index. - parent_field (Link to same Doctype) → Represents parent-child hierarchy. - old_parent (Data) → Stores previous parent for tracking changes.

Example:

class Category(NestedSet):
    nsm_parent_field = "parent_category"

2. Adding a Node

When creating a new record, set its parent field (e.g., parent_category).

Steps: 1. Create a new record. 2. Set the parent_category (if any). 3. Save the document. 4. The system will automatically calculate lft and rgt.

3. Moving a Node

To move a node: 1. Change the parent_category. 2. Save the document. 3. The system will reposition it correctly.

Validation: - Prevents assigning a node to its own descendant. - Updates all affected lft and rgt values.

4. Deleting a Node

1. Ensure the node has no children.
2. Delete the document.

If the node has children: - Deleting is not allowed unless you remove its children first.

Alternatively, use:

remove_subtree("Category", "Node Name")

to delete the node and its entire subtree.

5. Rebuilding the Tree

If inconsistencies occur, rebuild the tree:

rebuild_tree("Category")

This recalculates lft and rgt values for all records.

6. Querying the Tree Structure

Use the following functions:

A. Get Root Node

get_root_of("Category")

Returns the top-most node in the hierarchy.

B. Get Ancestors of a Node

get_ancestors_of("Category", "Node Name")

Returns all parent nodes up to the root.

C. Get Descendants of a Node

get_descendants_of("Category", "Node Name")

Returns all child nodes recursively.

7. Preventing Errors

• Loops Prevention: System ensures a node cannot be its own parent.
• Multiple Roots Prevention: Only one root node is allowed.
• Child Existence Validation: Nodes with children cannot be deleted.

8. Example Usage

A. Creating a Hierarchy

Electronics
 ├── Phones
 │   ├── Android
 │   └── iPhone
 ├── Laptops
 └── Accessories

To create this structure: 1. Add "Electronics" (Root). 2. Add "Phones" with parent_category = "Electronics". 3. Add "Android" and "iPhone" under "Phones". 4. Add "Laptops" and "Accessories" under "Electronics".

9. Handling Merging

• Merging is only allowed between:
  • Group-to-Group
  • Leaf-to-Leaf
• If merging is required, ensure both nodes have the same is_group value.

10. Best Practices

✅ Always use update_nsm(doc) in on_update.
✅ Ensure no circular references exist.
✅ Use rebuild_tree() after bulk updates.
✅ Avoid deleting non-empty groups.

Conclusion

The Nested Set Model (NSM) in Frappe efficiently manages hierarchical data. By following this guide, you can create, modify, and query tree structures seamlessly.